namespace DefaultNamespace
{
    /**
     *
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

        示例 1:
        
        输入: "abcabcbb"
        输出: 3 
        解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
        
        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public class SubstringLength
    {
        /// <summary>
        /// 滑动窗口解法
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LengthOfLongestSubstringMap(string s)
        {
            /**
             * 利用滑动窗口实现 [i,j) 左闭右开
             */
            int result = 0;

            int i = 0; //窗口左边界

            int j = 0; //窗口右边界

            Dictionary<string,int> windowMap = new Dictionary<string, int>();
            for (; j < s.Length; j++)
            {
                if (windowMap.ContainsKey(s[j].ToString()))  
                {
                    //如果字典中存在重复的元素
                    i = Math.Max(windowMap[s[j].ToString()], i);  //如果存在 那么左区间开始变化

                    windowMap.Remove(s[j].ToString());
                }

                result = Math.Max(result, j - i + 1);

                windowMap.Add(s[j].ToString(),j+1);
            }
            
            return result;
        }
        
        /// <summary>
        /// 暴力解法
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LengthOfLongestSubstring(string s)
        {
            int result = 0;
    
            int count = 0;
    
            while (count<s.Length)
            {
                int index = count;
                    
                List<string> cur = new List<string>();
                    
                for (; index < s.Length; index++)
                {
                    if (cur.Contains(s[index].ToString()))
                    {
                        if (cur.Count > result)
                        {
                            result = cur.Count;
                        }
                        break;
                    }
                    else
                    {
                        cur.Add(s[index].ToString());
                    }
                }
                count++;
            }
                
            return result;

        }
    }

}